package com.dyz.leetcode._09_heapAndPriorityQueue;

import java.util.Arrays;
import java.util.PriorityQueue;

public class _1046_lastStoneWeight {
    //O(n^2)
    public int lastStoneWeight(int[] stones) {
        int n = stones.length;
        for(int i=0; i<n-1; i++){
            Arrays.sort(stones);
            int y = stones[n-1];
            int x = stones[n-2];
            if(x==0){break;}
            stones[n-1] = y-x;
            stones[n-2] = 0;
        }
        return stones[n-1];
    }
    public int lastStoneWeight1(int[] stones) {
        int n = stones.length;
        if(n==1){return stones[0];}

        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->b-a);
        for (int i = 0; i <n ; i++) {
            queue.add(stones[i]);
        }

        while (queue.size()>1){
            int y = queue.remove();
            int x = queue.remove();
            int diff = y-x;
            if(diff>0){queue.add(diff);}
        }
        return queue.isEmpty()?0:queue.peek();
    }

}
